Vốn xuất thân từ Paphlagonia, Theodora là nhà quý tộc gốc Armenia. Tên gọi của cha mẹ bà được gìn giữ trong Theophanes Continuatus, một bộ biên niên sử nối tiếp do Theophanes Confessor viết ra. Cha của bà là Marinos, một drungarios, và mẹ là Theoktiste Phlorina. Một số nhà phả hệ học đương đại bao gồm Cyril Toumanoff và Nicholas Adontz, đã gợi ý mối liên kết của gia đình Theodora với dòng họ quý tộc Mamikonia gốc Armenia. Theo lời Nina Garsoïan trong bộ từ điển Oxford Dictionary of Byzantium thì "nghe qua có vẻ hấp dẫn, dù luận đề này không thể chứng minh được vì thiếu nguồn tư liệu."[1] Do đó giới phả hệ học đã gán cho Marinos thuộc về dòng dõi Mamikonia; ông cũng có thể là con của Artavazd Mamikonia, ngời đứng đầu dòng tộc này vào những năm 770. Artavazd cầm đầu một cuộc nổi loạn có quy mô lớn ở Armenia chống lại nhà Abbasid để rồi về sau bị đè bẹp trong trận Bagrevand năm 775, kể từ đó cả gia tộc mất đi quyền lực, và nhiều người trong số các thành viên trong dòng họ này đã tìm đường trốn tránh sang Byzantium. Manuel gốc Armenia, một vị tướng hàng đầu của Theophilos, chính là chú của bà. Theodora là một người em gái của Bardas và Petronas. Theophanes cũng ghi chép lại về ba chị em: Kalomaria, Sophia và Irene. Irene theo như đồn đại là đã kết hôn với Sergios, anh trai của Thượng phụ Photios I thành Constantinopolis.